package priv.pront.code.lanqiao.competition.course.date0401;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @Description:
 * @Author: pront
 * @Time:2023-04-01 17:21
 */
public class 迷宫与陷阱 {
    static int N, K, ans = -1;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static char[][] map;
    static boolean[][][] vis;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        K = scanner.nextInt();
        map = new char[N + 2][10000];
        vis = new boolean[N + 2][N + 2][11];
        String tempStr = scanner.nextLine();
        for (int i = 1; i <= N; i++) {
            tempStr = scanner.nextLine();
            for (int j = 0; j < tempStr.length(); j++) {

                map[i][j + 1] = tempStr.charAt(j);
            }
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(map[1][1] == '.' ? new Node(1, 1, 0, 0) : new Node(1, 1, 0, K));
        if (map[1][1] == '.') {
            vis[1][1][0] = true;
        } else {
            vis[1][1][K] = true;
        }
        while (!queue.isEmpty()) {
            Node tempNode = queue.poll();
            if (tempNode.x == N && tempNode.y == N) {
                ans = tempNode.step;
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x = tempNode.x + dx[i];
                int y = tempNode.y + dy[i];
                if ( x >= 1 && x <= N && y >= 1 && y <= N && map[x][y] != '#') {
                    if (map[x][y] == 'X' && tempNode.invincible > 0 && !vis[x][y][tempNode.invincible - 1]) {
                        vis[x][y][tempNode.invincible - 1] = true;
                        queue.offer(new Node(x, y, tempNode.step + 1, tempNode.invincible - 1));
                    } else if (map[x][y] == '%' && !vis[x][y][K]) {
                        vis[x][y][K] = true;
                        queue.offer(new Node(x, y, tempNode.step + 1, K));
                    } else if (map[x][y] == '.' && tempNode.invincible == 0 && !vis[x][y][0]) {
                        vis[x][y][0] = true;
                        queue.offer(new Node(x, y, tempNode.step + 1, 0));
                    } else if (map[x][y] == '.' && tempNode.invincible > 0 && !vis[x][y][tempNode.invincible - 1]) {
                        vis[x][y][tempNode.invincible - 1] = true;
                        queue.offer(new Node(x, y, tempNode.step + 1, tempNode.invincible - 1));
                    }
                }
            }
        }
        System.out.println(ans);
    }

    private static boolean valid(int newX, int newY) {
        return newX >= 1 && newY >= 1 && newX <= N && newY < N && map[newX][newY] != '#';
    }

     public static class Node {
        public int x;
        public int y;
        public int step;
        public int invincible;

        public Node(int x, int y, int steps, int wudi) {
            this.x = x;
            this.y = y;
            this.step = steps;
            this.invincible = wudi;
        }
    }
}
